MOD = 10**9 + 7
from collections import *
import sys
itr = (line for line in sys.stdin.read().split('\n'))
INP = lambda: next(itr)
def ni(): return int(INP())
def nl(): return [int(_) for _ in INP().split()]
def solve():
N = ni()
adj = [[] for _ in range(N)]
for i in range(N-1):
u, v = nl()
adj[u-1].append(v-1)
adj[v-1].append(u-1)
chs = [[] for _ in range(N)]
back = [[] for _ in range(N)]
q = [0]
vis = set(q)
while q:
q2 = []
for u in q:
for v in adj[u]:
if v in vis: continue
chs[u].append(v)
back[v].append(u)
q2.append(v)
vis.add(v)
q = q2
ps = [len(chs[u]) for u in range(N)]
D = [-1]*N
q = [u for u in range(N) if ps[u] == 0]
i = 0
order = []
while q:
q2 = []
for u in q:
order.append(u)
for v in back[u]:
ps[v] -= 1
if ps[v] == 0:
q2.append(v)
D[u] = i
q = q2
i += 1
pw = pow(2, N-1, MOD)
su = sum(d + 1 for d in D)
print(pw*su%MOD)
def main():
T = ni()
for _ in range(T):
solve()
if __name__ == '__main__':
main()
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <random>
using namespace std;
std::default_random_engine generator;
int rnd(int l, int r)
{
std::uniform_int_distribution<int> distribution(l, r);
return distribution(generator);
}
template<class T> inline T gcd(T a, T b)
{
if(a < 0) return gcd(-a, b);
if(b < 0) return gcd(a, -b);
return (b==0) ? a : gcd(b, a%b);
}
template<class T> inline T lcm(T a, T b)
{
return a / gcd(a, b) * b;
}
long long mod = 1000000007;
const double pi = 3.141592653589793238462643383279;
long long powmod(long long x, long long p)
{
if(p == 0)
return 1;
if(p&1)
return x * powmod(x*x%mod, p/2) % mod;
else
return powmod(x*x%mod, p/2) % mod;
}
long long factorial_mod(long long n)
{
long long res = 1;
for (long long i = 2; i <= n; ++i) {
res = (res * i) % mod;
}
return res;
}
long long intsqrt(long long x) {
long long sx = sqrt((double)x) + 1;
if (sx*sx <= x)
return sx;
else
return sx-1;
}
void dfs(int u, int p, vector<vector<int>> &g, vector<int> &depth)
{
for (int v : g[u]) {
if (v != p) {
dfs(v, u, g, depth);
}
}
for (int v : g[u]) {
if (v != p) {
depth[u] = max(depth[u], depth[v] + 1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cout.precision(12);
cout << fixed;
cin.tie(0);
int numTestCases = 1;
cin >> numTestCases;
for(int Case = 1; Case <= numTestCases; ++Case)
{
int n;
cin >> n;
long long pow2 = 1;
for (int i = 0; i < n-1; ++i) {
pow2 = pow2 * 2 % mod;
}
vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> depth(n);
dfs(0, -1, g, depth);
long long res = 0;
for (int i = 0; i < n; ++i) {
res = (res + pow2 * (1+depth[i]) % mod) % mod;
}
cout << res;
cout << endl;
//cout << "Case #" << Case <<": ";
}
return 0;
}
1607A - Linear Keyboard | EQUALCOIN Equal Coins |
XOREQN Xor Equation | MAKEPAL Weird Palindrome Making |
HILLSEQ Hill Sequence | MAXBRIDGE Maximise the bridges |
WLDRPL Wildcard Replacement | 1221. Split a String in Balanced Strings |
1002. Find Common Characters | 1602A - Two Subsequences |
1555A - PizzaForces | 1607B - Odd Grasshopper |
1084A - The Fair Nut and Elevator | 1440B - Sum of Medians |
1032A - Kitchen Utensils | 1501B - Napoleon Cake |
1584B - Coloring Rectangles | 1562B - Scenes From a Memory |
1521A - Nastia and Nearly Good Numbers | 208. Implement Trie |
1605B - Reverse Sort | 1607C - Minimum Extraction |
1604B - XOR Specia-LIS-t | 1606B - Update Files |
1598B - Groups | 1602B - Divine Array |
1594B - Special Numbers | 1614A - Divan and a Store |
2085. Count Common Words With One Occurrence | 2089. Find Target Indices After Sorting Array |